// https://leetcode.cn/problems/two-sum/?envType=problem-list-v2&envId=o01seMu2

// 算法复杂度 O(n)
pub fn two_sum(nums: &Vec<i32>, target: i32) -> Vec<i32> {
    for (i, item) in nums.iter().enumerate() {
        let rest = &nums[i+1..];
        if let Some(j) = rest.iter().position(|x| *x == target - item) {
            return vec![i as i32, (i +j + 1) as i32]
        }
    }
    vec![]
}

// 算法复杂度 O(1)
use std::collections::HashMap;
pub fn two_sum_2(nums: &Vec<i32>, target: i32) -> Vec<i32> {
    let mut m: HashMap<i32, i32> = HashMap::new();
    for (i, val) in nums.iter().enumerate() {
        match m.get(&(target - *val)) {
            Some(j) => {
                return vec![*j, i as i32];
            }
            None => {
                m.insert(*val, i as i32);
            }
        }
    }
    return vec![];
}
